package Leetcode.图;

import java.util.Arrays;

public class DijkstraAlgorithm {

    // 用于表示没有父节点的常量
    private static final int NO_PARENT = -1;

    private static void dijkstra_test(int[][] adjacencyMatrix, int startVertex) {
        int n = adjacencyMatrix.length;
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            dist[i] = Integer.MAX_VALUE;
            visited[i] = false;
        }

        int[] parents = new int[n];
        dist[startVertex] = 0;
        parents[startVertex] = NO_PARENT;

        for (int i = 0; i < n; i++) {
            int minDistance = Integer.MAX_VALUE;
            int minVertex= -1;
            //找一个未访问过，且距离最小的点
            for (int j = 0; j < n; j++) {
                if (!visited[j] && dist[j] < minDistance) {
                    minDistance = dist[j];
                    minVertex = j;
                }
            }
            visited[minVertex] = true;

            //从上述找到的最小的点出发，更新能够到达的最小距离
            for (int j = 0; j < n; j++) {
                int distance = adjacencyMatrix[minVertex][j];
                if (distance != Integer.MAX_VALUE && distance > 0
                        && ((minDistance + distance) < dist[j])) {
                    parents[j] = minVertex;
                    dist[j] = minDistance + distance;
                }

            }
        }
        printSolution(startVertex, dist, parents);
    }
    // Dijkstra算法实现
    private static void dijkstra(int[][] adjacencyMatrix, int startVertex) {
        // 获取顶点的数量
        int nVertices = adjacencyMatrix[0].length;

        // shortestDistances数组保存从起始顶点到其他所有顶点的最短距离
        int[] shortestDistances = new int[nVertices];

        // added数组标记顶点是否已经加入到最短路径树中
        boolean[] added = new boolean[nVertices];

        // 初始化所有距离为无穷大，added数组为false
        for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
            shortestDistances[vertexIndex] = Integer.MAX_VALUE;
            added[vertexIndex] = false;
        }

        // 起始顶点到自身的距离始终为0
        shortestDistances[startVertex] = 0;

        // parents数组用于存储最短路径树
        int[] parents = new int[nVertices];

        // 起始顶点没有父节点
        parents[startVertex] = NO_PARENT;

        // 为所有顶点找到最短路径
        for (int i = 1; i < nVertices; i++) {
            // 从未处理的顶点中找到距离最小的顶点
            int nearestVertex = -1;
            int shortestDistance = Integer.MAX_VALUE;
            for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
                if (!added[vertexIndex] && shortestDistances[vertexIndex] < shortestDistance) {
                    nearestVertex = vertexIndex;
                    shortestDistance = shortestDistances[vertexIndex];
                }
            }

            // 标记找到的最小距离顶点为已处理
            added[nearestVertex] = true;

            // 更新与最小距离顶点相邻的顶点的距离
            for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
                int edgeDistance = adjacencyMatrix[nearestVertex][vertexIndex];

                if (edgeDistance > 0 && ((shortestDistance + edgeDistance) < shortestDistances[vertexIndex])) {
                    parents[vertexIndex] = nearestVertex;
                    shortestDistances[vertexIndex] = shortestDistance + edgeDistance;
                }
            }
        }
        System.out.println(Arrays.toString(parents));
        // 打印结果
        printSolution(startVertex, shortestDistances, parents);
    }

    // 打印构建的距离数组和最短路径
    private static void printSolution(int startVertex, int[] distances, int[] parents) {
        int nVertices = distances.length;
        System.out.print("顶点\t距离\t路径");

        for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
            if (vertexIndex != startVertex) {
                System.out.print("\n" + startVertex + " -> ");
                System.out.print(vertexIndex + "\t\t");
                System.out.print(distances[vertexIndex] + "\t\t");
                printPath(vertexIndex, parents);
            }
        }
    }

    // 递归打印从起始顶点到当前顶点的路径
    private static void printPath(int currentVertex, int[] parents) {
        if (currentVertex == NO_PARENT) {
            return;
        }
        printPath(parents[currentVertex], parents);
        System.out.print(currentVertex + " ");
    }

    public static void main(String[] args) {
        // 邻接矩阵表示的图
        int[][] graph = {
                {0, 4, 0, 0, 0, 0, 0, 8, 0},
                {4, 0, 8, 0, 0, 0, 0, 11, 0},
                {0, 8, 0, 7, 0, 4, 0, 0, 2},
                {0, 0, 7, 0, 9, 14, 0, 0, 0},
                {0, 0, 0, 9, 0, 10, 0, 0, 0},
                {0, 0, 4, 14, 10, 0, 2, 0, 0},
                {0, 0, 0, 0, 0, 2, 0, 1, 6},
                {8, 11, 0, 0, 0, 0, 1, 0, 7},
                {0, 0, 2, 0, 0, 0, 6, 7, 0}
        };

        dijkstra(graph, 0);
    }
}